package dk.rafaelcouto.PhoneTone_Extractor;

public class FFT
{
    public static Complex[] cconvolve(final Complex[] array, final Complex[] array2) {
        if (array.length != array2.length) {
            throw new RuntimeException("Dimensions don't agree");
        }
        final int length = array.length;
        final Complex[] fft = fft(array);
        final Complex[] fft2 = fft(array2);
        final Complex[] array3 = new Complex[length];
        for (int i = 0; i < length; ++i) {
            array3[i] = fft[i].times(fft2[i]);
        }
        return ifft(array3);
    }
    
    public static Complex[] convolve(final Complex[] array, final Complex[] array2) {
        final Complex complex = new Complex(0.0, 0.0);
        final Complex[] array3 = new Complex[2 * array.length];
        for (int i = 0; i < array.length; ++i) {
            array3[i] = array[i];
        }
        for (int j = array.length; j < 2 * array.length; ++j) {
            array3[j] = complex;
        }
        final Complex[] array4 = new Complex[2 * array2.length];
        for (int k = 0; k < array2.length; ++k) {
            array4[k] = array2[k];
        }
        for (int l = array2.length; l < 2 * array2.length; ++l) {
            array4[l] = complex;
        }
        return cconvolve(array3, array4);
    }
    
    public static Complex[] fft(final Complex[] array) {
        final int length = array.length;
        Complex[] array2;
        if (length == 1) {
            array2 = new Complex[] { array[0] };
        }
        else {
            if (length % 2 != 0) {
                throw new RuntimeException("N is not a power of 2");
            }
            final double n = -6.283185307179586 / length;
            final Complex[] array3 = new Complex[length / 2];
            for (int i = 0; i < length / 2; ++i) {
                array3[i] = array[i * 2];
            }
            final Complex[] fft = fft(array3);
            for (int j = 0; j < length / 2; ++j) {
                array3[j] = array[1 + j * 2];
            }
            final Complex[] fft2 = fft(array3);
            array2 = new Complex[length];
            for (int k = 0; k < length / 2; ++k) {
                final double n2 = n * k;
                final Complex complex = new Complex(Math.cos(n2), Math.sin(n2));
                array2[k] = fft[k].plus(complex.times(fft2[k]));
                array2[k + length / 2] = fft[k].minus(complex.times(fft2[k]));
            }
        }
        return array2;
    }
    
    public static Complex[] ifft(final Complex[] array) {
        final int length = array.length;
        final Complex[] array2 = new Complex[length];
        for (int i = 0; i < length; ++i) {
            array2[i] = array[i].conjugate();
        }
        final Complex[] fft = fft(array2);
        for (int j = 0; j < length; ++j) {
            fft[j] = fft[j].conjugate();
        }
        for (int k = 0; k < length; ++k) {
            fft[k] = fft[k].times(1.0 / length);
        }
        return fft;
    }
    
    public static void show(final Complex[] array, final String s) {
        System.out.println(s);
        System.out.println("-------------------");
        for (int i = 0; i < array.length; ++i) {
            System.out.println(array[i]);
        }
        System.out.println();
    }
}
